package easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution_720 {
    public String longestWord(String[] words) {
        HashSet<String>[] array = new HashSet[31];
        for (String word : words) {
            int length = word.length();
            HashSet<String> set = array[length];
            if (set == null) {
                set = new HashSet<>();
            }
            set.add(word);
            array[length] = set;
        }
        for (int i = array.length - 1; i >= 0; i--) {
            Set<String> strings = array[i];
            if (strings == null) {
                continue;
            }
            List<String> list = new ArrayList<>();
            for (String string : strings) {
                boolean flag = true;
                char[] chars = string.toCharArray();
                for (int j = chars.length - 1; j > 0; j--) {
                    if (array[j] == null) {
                        flag = false;
                        break;
                    }
                    Set<String> subSet = array[j];
                    if (!subSet.contains(new String(chars, 0, j))) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(string);
                }
            }
            if (list.size()>0) {
                Collections.sort(list);
                return list.get(0);
            }
        }
        return "";
    }

    public static void main(String[] args) {
        Solution_720 model = new Solution_720();
        System.out.println(model.longestWord(new String[]{"w","wo","wor","worl", "world"}));
        System.out.println(model.longestWord(new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"}));
    }
}
